package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 988. 从叶结点开始的最小字符串
 * @author feizns
 * @since 2020/3/16
 */
public class SmallestFromLeaf {

    public static void main(String[] args) {
        System.out.println(smallestFromLeaf(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(4);
        ret.left = new TreeNode(0);
        ret.right = new TreeNode(1);
        ret.left.left = new TreeNode(1);
        return ret;
    }

    static String ans = "~";

    public static String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return ans;
    }

    private static void dfs(TreeNode root, StringBuilder builder) {
        if ( root != null ) {
            builder.append(to(root.val));
            if ( root.left != null || root.right != null ) {
                dfs(root.left, builder);
                dfs(root.right, new StringBuilder(builder));
            } else {
                String str = builder.reverse().toString();
                if ( ans.compareTo(str) > 0 )
                    ans = str;
            }
        }
    }

    private static char to(int x) {
        return (char)((int)'a' + x);
    }

}
